﻿#define _CRT_SECURE_NO_WARNINGS 1





// 时间/空间复杂度练习，旋转数组，消失的数字









//作业标题(876)
//1.下列有关大O表示法的说法错误的是 C
//
//
//作业内容
//A.大O表示法只是对程序执行时间的一个估算
//B.大O表示法只保留最高阶项
//C.大O表示法会保留一个系数来更准确的表示复杂度
//D.大O表示法一般表示的是算法最差的运行时间














//作业标题(905)
//3.分析以下函数的时间复杂度 D
//
//void fun(int n) {
//    int i = l;
//    while (i <= n)
//        i = i * 2;
//}
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(nlogn)
//D.O(logn)




















//作业标题(891)
//2.分析以下程序的时间复杂度 B
//
//for (int i = 0; i < n; i++)
//    for (int j = 0; j < n; j++)
//        a[i][j] = i * j;
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(nlogn)
//D.O(logn)























//
//作业标题(944)
//5.下面算法的时间复杂度是（A）
//
//int f(unsigned int n) {
//    if (n == 0 || n == 1)
//        return 1;
//    else
//        return n * f(n - 1);
//}
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(nlogn)
//D.O(logn)




















//作业标题(949)
//6.给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a + b的结果最接近sum，最快的平均时间复杂度是（A）
//
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(nlogn)
//D.O(logn)




//链接：https://www.nowcoder.com/questionTerminal/d5a859566bab460a8a9f56ad16800640
//来源：牛客网
//
//答案：O(n)
//思想类似于两端向中间扫描
//1、设定两个指针P1、P2，分别指向数组开始和结尾，即P1指向最小值，P2指向最大值；
//2、计算 * P1 + *P2 的值为 SUM，与 sum 比较，记录它们的差值 DIF 和 SUM，若 SUM<sum，P1++，若SUM>sum，P2--;
//3、重复以上过程直到DIF最小























//作业标题(959)
//2.分析以下函数的空间复杂度（B）
//
//int** fun(int n) {
//    int** s = (int**)malloc(n * sizeof(int*));
//    while (n--)
//        s[n] = (int*)malloc(n * sizeof(int));
//    return s;
//}
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(1)
//D.O(nlogn)
























//作业标题(954)
//1.如果一个函数的内部中只定义了一个二维数组a[3][6]，请问这个函数的空间复杂度为（C）
//
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(1)
//D.O(m * n)

























//作业标题(939)
//4.设某算法的递推公式是T(n) = T(n - 1) + n，T(0) = 1，则求该算法中第n项的时间复杂度为（A）
//
//
//作业内容
//A.O(n)
//B.O(n ^ 2)
//C.O(nlogn)
//D.O(logn)






//答案：A
//
//解析：
//
//T(n)
//
//= T(n - 1) + n
//
//= T(n - 2) + (n - 1) + n
//
//= T(n - 3) + (n - 2) + (n - 1) + n
//
//...
//
//= T(0) + 1 + 2 + ... + (n - 2) + (n - 1) + n
//
//= 1 + 1 + 2 + ... + (n - 2) + (n - 1) + n
//
//
//
//从递推公式中可以看到，第n项的值需要从n - 1开始递归，一直递归到0次结束，共递归了n - 1次
//
//所以时间复杂度为n




































































//作业标题(985)
//4.旋转数组
//
//作业内容
//4.旋转数组。
//
// 
// 
//https://leetcode.cn/problems/rotate-array/
//




// 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//
//
//
// 示例 1:
//
// 输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
// 输出 : [5, 6, 7, 1, 2, 3, 4]
// 解释 :
//	 向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
//	 向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
//	 向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]
// 示例 2 :
//
//	输入：nums = [-1, -100, 3, 99], k = 2
//	输出：[3, 99, -1, -100]
//	解释 :
//	向右轮转 1 步 : [99, -1, -100, 3]
//	向右轮转 2 步 : [3, 99, -1, -100]
//
//
//	提示：
//
//	1 <= nums.length <= 105
//	- 231 <= nums[i] <= 231 - 1
//	0 <= k <= 105
//
//
//	进阶：
//
//	尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
//	你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
//	通过次数592, 369提交次数1, 337, 991
//
// 
// 
// 
// 
//  
// 
// 超时有两种可能：
// 
// 1.效率超时
// 
// 2.死循环
// 
// 
// 
// 
// 
// 
// 
// 思路一：暴力求解
// 
// 
// 每次右旋一个元素，需要右旋几个元素就重复该过程几次
// 
// 
// 
void rotate(int* nums, int numsSize, int k) {
	// 排除重复的旋转周期
	k %= numsSize;

	// 右旋k个元素
	for (int i = 0; i < k; i++)
	{
		//保存最后一个元素
		int temp = nums[numsSize - 1];

		//所有元素向后移动一位
		for (int j = numsSize - 2; j >= 0; j--)
		{
			nums[j + 1] = nums[j];
		}

		//最后一个元素放入第一位
		nums[0] = temp;
	}

}
// 
// 时间复杂度：
// O(N*K)
// 
// 空间复杂度：
// O(1)
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 思路二：以空间换时间
// 
// 重新创建一个数组，
// 先拷贝后k个元素到新数组的前k个元素空间上，
// 之后再拷贝前N-k个数组到新数组的后N-k个元素空间上，
// 最后把新数组上所有的元素拷贝到旧数组上即可。
// 
// 
// 
void rotate(int* nums, int numsSize, int k) {
	// 排除重复的旋转周期
	k %= numsSize;

	//创建一个临时数组空间
	int* tp = (int*)malloc(numsSize * sizeof(int));// 变长数组：VS IDE下不支持，但是OJ一般都采用C99标准支持

	//移动后k个元素
	for (int i = 0; i < k; i++)
	{
		tp[i] = nums[numsSize - k + i];
	}

	//移动前numsSize-k个元素
	for (int j = 0; j < numsSize - k; j++)
	{
		tp[j + k] = nums[j];
	}

	//转移所有元素到nums
	for (int n = 0; n < numsSize; n++)
	{
		nums[n] = tp[n];
	}

	//释放空间
	free(tp);
	tp = NULL;

}
// 
// 时间复杂度：
// O(N)
// 
// 空间复杂度：
// O(N)
// 
// 
// 
// 
// 
// 
// 
// 调试：heap-buffer-overflow  ----  越界
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
//
// 
// 左旋：三步翻转法
// 
// 
// 
// 
// 左旋2个字符
// abcdef
// 
// 逆序前2个字符
// bcedef
// 
// 逆序后6-2个字符
// bafedc
// 
// 逆序全部字符
// cdefab
// 
// 
// 
// 
// 
// 
// 
// 右旋：三步法
// 
// 
// 
// 
// 右旋2个字符
// abcdef
// 
// 逆序后2个字符
// abcdfe
// 
// 逆序前6-2个字符
// dcbafe
// 
// 逆序全部字符
// efabcd
// 
// 
// 
// 
// 
// 
// 
// 
// 
void reverse(int* left, int* right)
{
	while (left < right)
	{
		int temp = *left;
		*left = *right;
		*right = temp;

		left++;
		right--;
	}
}

void rotate(int* nums, int numsSize, int k) {
	//排除重复的周期
	k %= numsSize;

	//逆序后k个元素
	reverse(nums + numsSize - k, nums + numsSize - 1);

	//逆序前numsSize-k个元素
	reverse(nums, nums + numsSize - k - 1);

	//逆序全部元素
	reverse(nums, nums + numsSize - 1);

}
// 
// 
// 
// 
// 
// 
//





































































//作业标题(2095)
//8.消失的数字
//
//作业内容
//数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//
//
//
//https://leetcode-cn.com/problems/missing-number-lcci
// 
// 
// 
// 
// 
// 
// 面试题 17.04. 消失的数字
//数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
//
//注意：本题相对书上原题稍作改动
//
//示例 1：
//
//输入：[3, 0, 1]
//输出：2
//
//
//示例 2：
//
//输入：[9, 6, 4, 2, 3, 5, 7, 0, 1]
//输出：8
// 
// 
// 
// 
// 
// 提供尽可能多的思路
// 用复杂度分析，然后实现最优的思路
// 
// 
// 
// 
// 
//
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
//思路1：求和相加
// 
// 
// (n+1)*n/2 - (a[0]+a[1]+...+a[n-1])
// 本应该所有数的总和 - 目前所有数的总和
// 
// 时间复杂度：O(N)  ---  前面计算的为常数级，后面则需要遍历当前数组
// 空间复杂度：O(1)  ---  前面需要创建一个临时变量保存本应该所有数的总和，后面需要一个循环变量
// 
// 
// 
// 注意：这里的numsSize数值本身就是(n)
// 
int missingNumber(int* nums, int numsSize) {
	// 目标数据总和
	int ret = (numsSize + 1) * numsSize / 2;

	// 目标-现有数据总和
	for (int i = 0; i < numsSize; ++i)
	{
		ret -= nums[i];
	}

	return ret;

}
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 思路2：
// qsort排序
// 
// 时间复杂度：O(logN*N)
// 空间复杂度：O(logN)
// 
// 冒泡排序
// 
// 时间复杂度：O(N^2)
// 空间复杂度：O(1)
// 
// 
// 
// 
// 
// 排除！！！
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 思路3：异或
// 
// 找单身狗：
// 若一个数组中所有的元素都是两两成对的，其中仅有一个元素是单独的，那么把整个数组的所有元素都两两异或起来，最终的值就是那个单独一个元素的值
// 
// 
// 
// 
// 现有数据循环相互两两异或的过程中每次与自增1的元素也同时异或即可
// 
// 时间复杂度：O(N)
// 空间复杂度：O(1)
// 
// 
// 
// 
int missingNumber(int* nums, int numsSize) {
	// 缺失的元素
	int x = 0;
	// 跟数组中已有元素异或 --- 下标0 ~ numsSize-1
	for (size_t i = 0; i < numsSize; ++i)
	{
		x ^= nums[i];
	}
	// 再跟0~numsSize的所有值异或
	for (size_t j = 0; j < numsSize + 1; ++j)
	{
		x ^= j;
	}

	return x;
}
// 
// 
// 
// 
// 